package com.yubest;

/**
 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 *  
 *
 * 示例 1：[图片] img/0024.jpg
 *
 *
 * 输入：head = [1,2,3,4]
 * 输出：[2,1,4,3]
 * 示例 2：
 *
 * 输入：head = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：head = [1]
 * 输出：[1]
 *  
 *
 * 提示：
 *
 * 链表中节点的数目在范围 [0, 100] 内
 * 0 <= Node.val <= 100
 *  
 *
 * 进阶：你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/2 14:01
 */
public class P0024 {

    public static void main(String[] args) {
        new Solution24().swapPairs(new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4)))));

        new Solution24().swapPairs(null);

        new Solution24().swapPairs(new ListNode(1));
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution24 {

    public ListNode swapPairs(ListNode head) {
        //哨兵位
        ListNode guard = new ListNode(0, head);
        //前节点
        ListNode pre = guard;
        //当前节点和下一节点，即是要互换的两个节点
        //当前节点
        ListNode cur = head;
        //下一节点
        ListNode next = null != head ? head.next : null;
        while (cur != null && next != null) {
            //当前节点指向下一节点的下一节点
            cur.next = next.next;
            //下一节点指向当前节点
            next.next = cur;
            //前节点指向下一节点
            pre.next = next;

            //移动前节点，当前节点，下一节点到下次需要交换的位置处
            pre = cur;
            cur = pre.next;
            next = null != cur ? cur.next : null;
        }
        return guard.next;
    }
}
